package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/9/16 4:26 下午
 * <p>
 * 游戏币
 * 小赛酷爱游戏，在他卧室的抽屉里有n个游戏币，总面值m，游戏币的设置有1分的，2分的，5分的，而在小赛所拥有的游戏币中有些面值的游戏币可能没有，求一共有多少种可能的游戏币组合方式？
 * <p>
 * <p>
 * <p>
 * 输入描述
 * 输入两个数n(游戏币的个数)，m(总面值)。
 * <p>
 * <p>
 * <p>
 * 输出描述
 * 请输出可能的组合方式数；
 */
public class GetCateCount {

    public static void main(String[] args) {

        List<Integer> selectList = new ArrayList();

        selectList.add(1);
        selectList.add(2);
        selectList.add(5);

        int res = 0;
        int ret = getCateCount(3,5 , selectList, res);

        System.out.println(ret);

    }

    private static int getCateCount(int count, int sum, List<Integer> selectList, int res) {

        //选择列表  1,2,5
        if (count == 0 || sum <= 0) {
            return res;
        }

        for (Integer val : selectList) {
            if (sum < val) {
                return res;
            }

            if (sum == val) {
                return 1;
            }

            res += getCateCount(count - 1, sum - val, selectList, res);
        }

        return res;
    }
}
